package a2022.a20220905;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    static Map<String, Integer> map = new HashMap<>();
    static List<TreeNodeTwo> ans = new ArrayList<>();
    public static void main(String[] args) {
        TreeNodeTwo root = new TreeNodeTwo(1,
                new TreeNodeTwo(2,
                        new TreeNodeTwo(4),
                        null),
                new TreeNodeTwo(3,
                        new TreeNodeTwo(2,
                                new TreeNodeTwo(4),
                                null),
                        new TreeNodeTwo(4)));
        List<TreeNodeTwo> duplicateSubtrees = findDuplicateSubtrees(root);
        for (int i = 0; i < duplicateSubtrees.size(); i++) {
            System.out.println(Codec.serialize(duplicateSubtrees.get(i)));
        }
    }
    public static List<TreeNodeTwo> findDuplicateSubtrees(TreeNodeTwo root) {
        dfs(root);
        return ans;
    }
    static String dfs(TreeNodeTwo root) {
        if (root == null) return " ";
        StringBuilder sb = new StringBuilder();
        sb.append(root.val).append("_");
        sb.append(dfs(root.left)).append(dfs(root.right));
        String key = sb.toString();
        map.put(key, map.getOrDefault(key, 0) + 1);
        if (map.get(key) == 2) ans.add(root);
        return key;
    }
}
